/**
 * 
 */
package logic.huffman;

import io.ImageReader;

import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.Comparator;
import java.util.HashMap;
import java.util.PriorityQueue;

import datamodel.RGB;
import datamodel.huffman.tree.Tree;
import datamodel.huffman.tree.TreeNode;

/**
 * Implements the Huffman algorithm for an image.
 * 
 * @author Kevin Munk, Jakob Karolus
 * @version 1.0
 * 
 */
public class HuffmanTree {
	

	/**
	 * returns a HuffmanTree which is based on the given file (an image)<br>
	 * Less "weighted"(less probability) subtrees will be placed right.
	 * 
	 * @param file the file to load and generate the tree
	 * @return the Huffman tree for the file
	 * @throws FileNotFoundException
	 * @throws IOException
	 */
	public static Tree getHuffmanTree(String file) throws FileNotFoundException, IOException{
		ImageReader ir = new ImageReader(file); 
		HashMap<RGB, Integer> map = new HashMap<RGB, Integer>();
		
		for (RGB rgb : ir){
			if(map.containsKey(rgb)){
				map.put(rgb, map.get(rgb)+1);
			}else {
				map.put(rgb, 1);
			}
		}
		
		PriorityQueue<TreeNode> sortedQueue = new PriorityQueue<TreeNode>(map.size(), new TreeNodeComparator());
		for (RGB rgb : map.keySet()) {
			sortedQueue.add(new TreeNode(rgb, map.get(rgb)));
		}
		
		while(sortedQueue.size() > 1) {
			TreeNode rightNode = sortedQueue.poll();
			TreeNode leftNode =  sortedQueue.poll();
			TreeNode node = new TreeNode(rightNode.getOccurance() + leftNode.getOccurance(), leftNode, rightNode);
			sortedQueue.add(node);
		}
		return new Tree(sortedQueue.peek());
	}
	
	static class TreeNodeComparator implements Comparator<TreeNode> {
		@Override
		public int compare(TreeNode node1, TreeNode node2) {
			return node1.getOccurance() - node2.getOccurance();	
		}
	}
}